#include<stdio.h>
#include<stdlib.h>

struct LNode
{
	int data;
	struct LNode *next;
};
struct LNode *CreateListT(struct LNode * L, int n)
{
	//1.先定义一个节点指针s指向新生结点，先建立一个头结点
	struct LNode *s;
	L=(struct LNode *)malloc(sizeof(struct LNode));
	L->next=NULL;
	//2循环输入数据,生成新的结点,每个新生节点加入到头结点后。
	//数据域赋值，指针域更换
	int data;
	while(n)
	{
		scanf("%d",&data);
		s=(struct LNode *)malloc(sizeof(struct LNode));
		s->data=data;
		s->next=L->next;
		L->next=s;
		n--;
	}
	return L;
}

//带头结点的尾插法创建单链表
struct LNode *CreateListF(struct LNode *L,int n)
{
	//1.先建立一个头结点，r始终指向尾结点开始指向头结点
	struct LNode *r,*s;//s指向新生结点，r指向尾结点
	L=(struct LNode *)malloc(sizeof(struct LNode));
	r=L;
	//2循环输入数据,生成新的结点，数据域赋值，指针域更换
	int data;
	while(n)
	{
		scanf("%d",&data);
		s=(struct LNode *)malloc(sizeof(struct LNode));
		s->data=data;
		r->next=s;
		r=s;
		n--;
	}
	//3.最后尾指针置位空
	r->next=NULL;
	return L;
}

//合并链表功能
struct LNode *ConnectLinkList(struct LNode * L1,struct LNode *L2)
{
	struct LNode *temp;
	if(L1->next==NULL) return L2;	
	else
	{
		if(L2->next!=NULL)
		{
			temp=L1;
			while(temp->next) temp=temp->next;
			temp->next=L2;
		}
	}
	return L1;
}

/*本实例实现单链表的逆置，主要算法思想是:
将单链表的节点按照从前往后的顺序依次取出，并依次插入到头节点的位置*/

//单链表的逆置功能
struct LNode *reverse(struct LNode *L)
{
	struct LNode *temp1;
	struct LNode *temp2;
	
	if(L->next!=NULL&&L->next->next!=NULL)	//如果L头结点有数据节点且数据节点不止一个
	{
		temp1=L;				//temp1获取头结点地址
		temp2=temp1->next;		//temp2获取头节点的下一个数据节点
		temp1->next=NULL;		//断开temp节点的数据节点
		while(temp2)
		{
			temp1=temp2;		//数据节点赋值给temp1
			temp2=temp2->next;  //temp2数据节点指向下一个
			temp1->next=L->next;      //依次插入到头节点的位置
			L->next=temp1;			//头结点指针域变化
		}
		return L;
	}
	return L;
}
struct LNode *part_reverse(struct LNode *L,int m,int n)
{
	/*
step 1：我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置开始反转，在多了一个表头的情况下就能保证第一个节点永远不会反转，不会到后面去。
step 2：使用两个指针，一个指向当前节点，一个指向前序节点。
step 3：依次遍历链表，到第m个的位置。
step 4：对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向。
step 5：返回时去掉我们添加的表头。	
	*/
	
	//加个表头
	struct LNode *res=NULL;
    res->next = L;
    
    //前序节点
    struct LNode *pre = res;
    //当前节点
    ListNode cur = head;
    //找到m
    for(int i = 1; i < m; i++)
    {
        pre = cur;
        cur = cur->next;
    }
	 //从m反转到n
	for(i=m;i<n;i++)
	{
		struct LNode*temp=cur->next;
	
	}
	 
}

void printfList(struct LNode *L)
{
	struct LNode *s=L->next;
	while(s!=NULL)
	{
		printf("%d ",s->data);
		s=s->next;
	}
	printf("\n");
}

int main()
{
	printf("输入你想创建的链表节点数:\n");
	int num;
	scanf("%d",&num);
	
	struct LNode *L;
	
	L=CreateListF(L,num);

	//打印
	printf("逆置前:\n");
	printfList(L);

	printf("逆置后:\n");
	//struct LNode* rev= reverse(L);
	//printfList(rev);

	struct LNode * part_rev=part_reverse(L,2,4);
	printfList(part_rev);
	
	return 0;
}



